1. Field of the Invention
The present invention relates to data generating device and control method thereof, data analyzing device and control method thereof, data processing system, program and machine-readable storage medium. Particularly, the present invention relates to technology for efficiently analyzing variable-length data, in particular technology for efficiently analyzing public key certificates.
2. Description of the Related Art
As digital data including text data and image data flows through wide-area networks such as the internet, there is a danger that the data might be altered by a third party, since digital data is easily modified. In light of this danger, a technology known as a digital signature is known as a method of authenticating data for preventing alteration, making it possible for a recipient to detect whether or not received data has been altered. Digital signature technology also has functionality for preventing spoofing, repudiation, and the like, on the internet, and not just data alteration.
<<Digital Signatures>>
FIG. 10 is a schematic drawing showing a signature creation process and a signature authentication process. An overview of digital signature technology is given with reference to this drawing. Hash functions and public key encryption are used in generating digital signature data. Hereafter, a private key shall be Ks2106, and a public key shall be Kp2111.
When generating a digital signature, a hash process 2102 is applied to entered data (message) M2101, and a digest H(M) (2103), which is fixed-length data, is calculated. The hash function described below is used in the hash process 2102. Next, a conversion process 2104 is applied to this fixed-length data H(M) using the private key Ks2106, thereby creating digital signature data S (2105). The sender of the data sends the digital signature data S (2105) and the entered data (M2101) to the recipient after these processes.
During an authentication process 2112, the recipient first applies a conversion (decryption) process to the digital signature data S (2110) with the public key Kp2111 and acquires the data acquired thereby. Next, whether or not that data matches the data 2109 acquired by applying the hash process 2108 to the entered data M2107 is authenticated. As a result (2113) of this authentication, if the two sets of data do not match, it is judged that the data M has been altered, and if the two sets of data do match, it is judged that no alteration has been done. The recipient can thus detect the presence of alterations.
Moreover, digital signature methods include known RSA and DSA (described in detail below) and other methods based on public key encryption. The security of these digital signatures lies in the difficulty arising out of the computational complexity of forging a signature or cryptanalyzing a private key for an entity other than the possessor of the private key.
(Hash Functions)
Hash functions are described next. Hash functions are used together with the digital signature process in digital signature methods to reduce the volume of data to be computed through irreversible compression of the signed data, and thereby reduce the amount of time for the signature appending process. The hash function has functionality for applying a process to the entered data M with an arbitrary length and generating output data H(M) with a fixed length. In this case, the output H(M) is called the hash data of clear text data M.
In particular, one-way hash functions are characterized in that, when data M is received, the calculation of a clear text data M′ in which H(M′)=H(M) is difficult in terms of computational complexity. MD2, MD5, SHA-1, and other standard algorithms are known as such one-way hash functions.
(Public Key Encryption)
Public key encryption is described next. Public key encryption is characterized by using two corresponding keys, data encrypted with one key being impossible to decrypt with the other key. One of these two keys is called the public key, and is used disclosed to the outside. The other key is called the private key, and it is kept confidential and only used by the owner.
RSA signatures, DSA signatures, Schnorr signatures, and others are known as digital signatures used in public key encryption methods. The RSA signature disclosed in R. L. Rivest, A. Shamir and L. Adleman: “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM, v. 21, n. 2, pp. 120-126, February 1978, and the DSA signature disclosed in Federal Information Processing Standards (FIPS) 186-2, Digital Signature Standard (DSS), January 2000 are described as examples.
(RSA Signatures)
Generate primes p and q and let n=pq. Let λ(n) be the least common multiple of p−1 and q−1. Select an appropriate element e co-prime with λ(n), and let d=1/e(mod λ(n)). The public key is e and n, and the private key is d. Let H( ) be the hash function.
[Creation of RSA Signature] Signature Creation Procedure for Document M
Let s:=H(M)d(mod n) be the signature data.
[Verification of RSA Signature] Verification Procedure for Signature (s,T) Related to Document M.
Verify whether or not H(M)=se(mod n) is true. If it is true, then determine that no alteration has taken place. If it is not true, then determine that alteration has taken place.
(DSA Signatures)
Let p and q be primes and let p−1 divide q. Let g be the origin (generator) for order q, arbitrarily selected from Zp* (the multiplicative group wherein 0 is omitted from the cyclic group Zp of order p). Let x selected arbitrarily from Zp* be the private key, and let y:=gx(mod p) be the corresponding public key y. Let H( ) be the hash function.
[Creation of DSA Signature] Signature Creation Procedure for Document M
1) Select α from Zq arbitrarily and let T:=(gαmod p) mod q.
2) Let c:=H(M).
3) Let s:=α−1(c+xT) mod q, and (s,T) be the signature data.
[Verification of DSA Signature] Verification Procedure for Signature (s,T) Related to Document M.
Verify whether T=(gh(M)s^(−1)yTs^(−1) mod p) mod q is true. If it is true, then determine that no alteration has taken place. If it is not true, then determine that alteration has taken place.
<<Public Key Authentication Infrastructure>>
In client-server communication, user authentication is often needed when a client accesses server resources. A well-known technology used in user authentication is public key certificates such as ITU-T Recommendation X.509 and the like (ITU-T Recommendation X.509/ISO/IEC 9594-8: “Information technology—Open Systems Interconnection—The Directory: Public-key and attribute certificate frameworks”). A public key certificate is data guaranteeing that a public key corresponds to the user thereof, and to which is applied a digital signature by a trustworthy third-party known as a certification authority. For example, user authentication using SSL (Secure Sockets Layer) implemented by a browser is performed based on verifying whether or not the user has the private key corresponding to the public key contained in the public key certificate presented by the user.
By having signatures from certification authorities, public key certificates can be trusted as regards information pertaining to public keys of users and servers contained in the public key certificate. In other words, the trustworthiness of the information contained in the public key certificates is founded on the security of the digital signatures by the certification authorities. For this reason, if the private key used in creating the signature of a certification authority was leaked or became compromised, all the public key certificates issued by that certification authority would lose their trustworthiness and become invalid.
ITU-T Recommendation X.509 v.3, which is an example of a public key certificate, contains the ID and public key information of the certified entity (subject) as signed data by the certification authority The signature data of the certification authority is generated by computing the signature using, for example, the RSA algorithm described above on a digest in which a hash function has been applied to the signed data. Moreover, the signed data is provided with optional fields known as extensions, making it possible to include unique and new extension data in the application or protocol.
(X.509 v.3 Format)
FIG. 11 is a view showing a typical format of a public key certificate defined in X.509 v.3. The information stored in each field is described below.
A version 2201 stores the version of X.509. This field is optional, and if omitted expresses v1. A serialNumber 2202 stores a serial number uniquely allocated to this public key certificate by a certifying authority. A signature 2203 stores the signature method of the public key certificate. An issuer 2204 stores the X.500 identification name of the certifying authority which is the issuer of the public key certificate. A validity 2205 stores the expiration date of the public key (starting date and time and ending date and time). A subject 2206 stores the X.500 identification name of the owner of the private key corresponding to the public key contained in the certificate. A subjectPublicKeyInfo 2207 stores the public key which is certified.
An issuerUniqueIdentifier 2208 and a subjectUniqueIdentifier 2209 are optional fields added in v2. These store the unique identifier of the certifying authority and the unique identifier of the owner.
An extensions field 2210 is an optional field added in v3. These contain a three-part group made up of an extension identifier (extnId) 2211, an extension value (extnValue) 2213, and a critical bit (critical) 2212. The v3 extensions field 2210 may include not only the standard extension set forth in X.509, but also unique and new extensions. For this reason, how to authenticate the v3 extensions depends on the application. Moreover, the critical bit 2212 expresses whether these extensions are required or can be ignored.
The certifying authority generates a signature 2214 using the private key of the certifying authority on the data constituting the above public key certificate, and appends this to the public key certificate. The user of the public key certificate can use the signature 2214 to verify the legitimacy of the public key certificate.
(Analysis of the Public Key Certificate)
Use of the digital signature technology described above has the effect of preventing spoofing, data alteration, repudiation, and so on, on the internet. The infrastructure is in place for public key certificates to circulate as an infrastructure of trust having this effect. This infrastructure of trust is being used in more varied devices in recent years, even being used in digital home appliances, portable telephones, PDAs, and more, in addition to PCs and servers. The computational cost required for analyzing public key certificates therefore needs to be small enough for portable terminals, for example, to be able to compute them.
However, the X.509 public key certificate used as the de facto standard format for public key certificates is written in ASN.1, a general descriptive notation for variable-length data, and DER, the encoding method thereof (ISO/IEC 8825-1:1995 Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER), and Distinguished Encoding Rules (DER)). Therefore, devices which analyze public key certificates have had not only to execute processes for decryption computation but also for parsing ASN.1, or in other words analyzing the DER encoding method which is variable-length data, which required a certain level of computational cost. In other words, in order to use the infrastructure of trust afforded by X.509 public key certificates, devices have had to analyze variable-length data, which has entailed computational cost.
In light of this situation, constitutions have been known whose purpose is to allow use of the public key infrastructure without having to parse ASN.1 data and other types of variable-length data. Such constitutions can be broadly divided into two methods.
(1) The first is a method for reducing the computational cost involved in verification processes by using light public key certificates, such as SPKI (C. Ellison, SPKI Certificate Theory, Request for Comments 2693, IETF, September 1999). When reading SPKI, there is no need to parse ASN.1, and neither is there as much information as X.509, which means that it can be used easily in digital home appliances and portable telephones, etc., with a low amount of CPU resources.
(2) The other is a method in which devices for which executing a parse process for ASN.1 is difficult entrust processing to the authority, which performs the signature verification, signature appending, and other processes as a proxy. One known example of this is XKMS (XML Key Management Specification (XKMS 2.0), http://www.w3.org/TR/xkms2/, W3C Candidate Recommendation 5 Apr. 2004).
However, the domains which can be authenticated with method (1) are limited, and there is no compatibility with X.509. It is therefore difficult to establish interoperability with the certification infrastructure already popular on the internet.
Moreover, with method (2), communication between the authority (server) and device must be done in a trusted manner. This means that a separate mechanism, such as a prescribed authentication method, must be provided in order to perform secure communication between the server and the device. Furthermore, in order to use XKMS, the XML must also be parsed separately.
The above problems are not limited to analysis of public key certificates. In other words, conventional constitutions have been incapable of low computational cost analysis of all kinds of variable-length data described using existing variable-length data formats, including public key certificates.